#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int N = 5e4, mod = 20120427;
unordered_map<ll, int> id;
vector<ll> ca;
int A[20], pw[20], f[20][N], g[20][N], af[20], ag[20], cnt;
ll l, r, k;
inline void up(int &a, int b) { a = a + b >= mod ? (a + b)%mod : a + b;}

int ID(ll x){
    if(!id.count(x)) {
        id[x] = cnt++;
        ca.push_back(x);
    }
    return id[x];
}

void pre(){
    pw[0] = 1;
    for (int i = 1; i <= 19 ; ++i) {
        pw[i] = pw[i-1]*10%mod;
    }
    for (int i = 0; i <= 9; ++i) {
        f[1][ID(i)] ++;
        g[1][ID(i)] = i;
    }

    for (int p = 2; p <= 19 ; ++p) {
        int tcnt = cnt;
        for (int j = 0; j < tcnt; ++j) {
            ll x = ca[j];
            int pr = ID(x);
            for (int n = 0; n <= 9 ; ++n) {
                int nx = ID(n*x);
                up(f[p][nx], f[p-1][pr]);
                up(g[p][nx], (1ll*n*pw[p-1]%mod*f[p-1][pr] + g[p-1][pr])%mod);
            }
        }

    }
    for (int i = 1; i <= 19; ++i) {
        for (int j = 0; j < cnt; ++j) {
            up(af[i], f[i][j]);
            up(ag[i], g[i][j]);
        }
    }
}

int dfs(int p, int pre, ll K, bool flg, bool fir){
    if(p == 0) return K==1?pre:0;
    if(!id.count(K)) return 0;
    if(flg && !fir) return (1ll*pre*pw[p]%mod *f[p][ID(K)] + g[p][ID(K)])%mod;

    int x = flg? 9:A[p];
    int ans = 0;
    if(fir) up(ans, dfs(p-1, pre, K, flg||0<x, true));
    for (int i = 1; i <= x; ++i) {
        if(K%i==0) up(ans, dfs(p-1, (pre*10+i)%mod, K/i, flg||i<x, false));
    }
    return ans;
}

int dfs0(int p, int pre, bool zero, bool flg, bool fir){
    if(p == 0) return zero? pre:0;
    if(flg && !fir){
        if(!zero)return (1ll*pre * pw[p] %mod *f[p][ID(0)] + g[p][ID(0)])%mod;
        else return (1ll*pre * pw[p] %mod *af[p] + ag[p])%mod;
    }
    int x = flg? 9:A[p];
    int ans = 0;
    for (int i = 0; i <= x; ++i) {
        up(ans, dfs0(p-1, (pre*10+i)%mod, zero||(i==0&&!fir), flg||i<x, fir&&i==0));
    }
    return ans;
}

int cal(ll x){
    int p = 0;
    while (x) {
        A[++p] = x%10;
        x /= 10;
    }
    if(k) return dfs(p, 0, k, false, true);
    else return dfs0(p, 0, false, false, true);
}


signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    pre();
//    for (int i = 0; i < 19; ++i) {
//        cout << f[i][id[10]] << endl;
//    }
    int T; cin >> T;
    while (T--){
        cin >> l >> r >> k;
        cout << ((cal(r) - cal(l-1))+mod)%mod << endl;
    }
    return 0;
}